<!DOCTYPE html>
<html lang="zh-hans">

<head>
    
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no" />
<meta name="HandheldFriendly" content="True" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
<meta name="generator" content="Hugo 0.109.0">


<link rel="shortcut icon" href="https://cdn.jsdelivr.net/gh/dsrkafuu/dsr-cdn-main@1/images/favicons/dsrca.ico" />



<title>ACO蚁群算法 - OffSummer</title>


<meta name="author" content="RQY" />


<meta name="description" content="A minimal Hugo theme with nice theme color." />


<meta name="keywords" content="机器学习" />


<meta property="og:title" content="ACO蚁群算法" />
<meta name="twitter:title" content="ACO蚁群算法" />
<meta property="og:type" content="article" />
<meta property="og:url" content="/post/aco/" /><meta property="og:description" content="概述
蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素（pheromones）浓度，并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。" />
<meta name="twitter:description" content="概述
蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素（pheromones）浓度，并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。" /><meta property="og:image" content="/img/og.png" />
<meta name="twitter:card" content="summary_large_image" />
<meta name="twitter:image" content="/img/og.png" />


<style>
    @media (prefers-color-scheme: dark) {
        body[data-theme='auto'] img {
            filter: brightness(60%);
        }
    }

    body[data-theme='dark'] img {
        filter: brightness(60%);
    }
</style>




<link rel="stylesheet" href="/assets/css/fuji.min.b4a21b5d3eb1d0a51297e31230a65fc25e387843e45ec3a2d9176cd8d163c216d99b9b13a618b28f537c3b559ec8a408183b0fbfad48daddb9befa7d3ef90eed.css" integrity="sha512-tKIbXT6x0KUSl&#43;MSMKZfwl44eEPkXsOi2Rds2NFjwhbZm5sTphiyj1N8O1WeyKQIGDsPv61I2t25vvp9PvkO7Q==" />








</head>

<body
  data-theme="auto"
  data-theme-auto='true'
  >
    <script data-cfasync="false">
  
  var fujiThemeData = localStorage.getItem('fuji_data-theme');
  
  if (!fujiThemeData) {
    localStorage.setItem('fuji_data-theme', 'auto');
  } else {
    
    if (fujiThemeData !== 'auto') {
      document.body.setAttribute('data-theme', fujiThemeData === 'dark' ? 'dark' : 'light');
    }
  }
</script>

    <header>
    <div class="container-lg clearfix">
        <div class="col-12 header">
            <a class="title-main" href="/">OffSummer</a>
            
            <span class="title-sub">Summer is going, but autumn does not come yet.</span>
            
        </div>
    </div>
</header>

    <main>
        <div class="container-lg clearfix">
            
            <div class="col-12 col-md-9 float-left content">
                
<article>
    
    <h2 class="post-item post-title">
        <a href="/post/aco/">ACO蚁群算法</a>
    </h2>
    <div class="post-item post-meta">
        <span><i class="iconfont icon-today-sharp"></i>&nbsp;0001-01-01</span>

<span><i class="iconfont icon-file-tray-sharp"></i>&nbsp;2167 字</span>
<span><i class="iconfont icon-time-sharp"></i>&nbsp;5 分钟</span>
<span><i class="iconfont icon-pricetags-sharp"></i>&nbsp;<a href="/tags/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0">机器学习</a>&nbsp;</span>

    </div>
    
    <div class="post-content markdown-body">
        <h2 id="概述">概述</h2>
<p>蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的<strong>信息素（pheromones）浓度</strong>，并<strong>倾向于往信息素浓度高</strong>的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。这种<strong>正反馈机制</strong>使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间<strong>蒸发</strong>，最终所有的蚂蚁都在最优路径上行进。</p>
<h2 id="基本模型">基本模型</h2>
<h3 id="蚂蚁">蚂蚁</h3>
<p>蚂蚁个体是具有随机行为的简单个体，其组成的群体有较强的自组织性和智能性。</p>
<h3 id="信息素">信息素</h3>
<p>蚂蚁行进路径越短，留在路径上的信息素也会越多，影响其周围蚂蚁选择路径的概率也越大。这是一种<strong>正反馈机制</strong>。</p>
<h3 id="信息素更新法则">信息素更新法则</h3>
<h4 id="ant-cycle模型">Ant-Cycle模型</h4>
<p><a href="ACO%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95%20473e013a7902432ebfea6a2452d1c181/ACO.mp4">ACO.mp4</a></p>
<p><img class="img-zoomable" src="ACO%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95%20473e013a7902432ebfea6a2452d1c181/Untitled.png" alt="Untitled" />
</p>
<p>$$
\Delta\tau(r,s)=\sum_{k=1}^{m}\tau^k_{ij}(t)
$$</p>
<p>$\rho$表示信息素挥发系数，$\tau_{ij}(t)$表示本次循环中城市$i$与城市$j$之间的路径的信息素的残留量。在初始情况下，$\tau_{ij}(0)=0$，$\tau_{ij}^k(t)$表示蚂蚁$k$在本次循环中城市$i$与城市$j$之间的路径的信息素的残留量。</p>
<p>优点：鲁棒性强、可以并行分布式计算、易与其他算法相结合。</p>
<p>缺点：容易进入局部最优、搜索时间过长、收敛速度慢。不适合高效率、高精度的求解优化问题</p>
<p>$$
\tau(r,s)=(1-\rho)\tau(r,s)+\rho\Delta\tau(r,s).
$$</p>
<p>改进方向主要有三个方面：信息素更新策略、路径选择策略、与其他算法融合。</p>
<h4 id="精华蚂蚁系统eas"><strong>精华蚂蚁系统EAS</strong></h4>
<p>它在原AS信息素更新原则的基础上增加了一个对至今最优路径的强化手段：在每轮信息素更新完毕后，搜索到至今最优路径(用Tb表示)的那只蚂蚁将会为这条路径添加额外的信息素。引入这种额外的信息素强化手段有助于更好地引导蚂蚁搜索的偏向，使算法更快收敛。</p>
<h4 id="最大最小蚂蚁系统mmas"><strong>最大最小蚂蚁系统MMAS</strong></h4>
<p><a href="ACO%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95%20473e013a7902432ebfea6a2452d1c181/MMAS.mp4">MMAS.mp4</a></p>
<p><a href="https://www.notion.so" target="_blank">https://www.notion.so</a></p>
<blockquote>
<p><a href="https://blog.csdn.net/yy2050645/article/details/86653435" target="_blank">MMAS_yy2050645的博客-CSDN博客_mmas算法</a></p>
</blockquote>
<p>MMAS在基本AS算法的基础上进行了四项改进：</p>
<ol>
<li>只允许迭代最优蚂蚁（在本次迭代构建出最短路径的蚂蚁），或者至今最优蚂蚁释放信息素。如果只使用历史最优解的话那么有可能会造成算法过早收敛，算法的开发性强，但是探索性较弱，有可能会陷入局部最优，而使用当前代最优解可以一定程度避免这种情况的发生。采用混合方式来进行信息素更新可以提高算法的性能。</li>
<li>信息素量大小的取值范围被限制在一个区间[т_min, т_max]内。当信息素浓度也被限制在一个范围内以后，位于城市i的蚂蚁k选择城市j作为下一城市的概率也将被限制在一个区间内。<strong>算法有效避免了陷入停滞状态</strong>（所有蚂蚁不断重复搜索同一条路径）的可能性。</li>
<li>信息素初始值为信息素取值区间的上限，并伴随一个较小的信息素蒸发速率。</li>
<li>每当系统进入停滞状态，问题空间内所有边上的信息素量都会被重新初始化。当算法已经收敛或接近收敛时，采用公式$\tau(i,j)=\tau(i,j)+\delta(\tau_{max}-\tau(i,j)),0 \lt \delta \lt 1$调整信息素，这样可以缩小当前最优解的路段信息素量与非当前最优解路段的信息素量的差值，从而使得蚂蚁有可能选择非当前最优解，从而增加算法的探索性。</li>
</ol>
<h4 id="蚁群系统acs">蚁群系统ACS</h4>
<p><a href="ACO%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95%20473e013a7902432ebfea6a2452d1c181/ACS.mp4">ACS.mp4</a></p>
<p><img class="img-zoomable" src="ACO%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95%20473e013a7902432ebfea6a2452d1c181/Untitled%201.png" alt="Untitled" />
</p>
<blockquote>
<p><a href="https://blog.csdn.net/weixin_42379024/article/details/104336654" target="_blank">ACS解决TSP问题的简单实现（C++）_小克林的博客-CSDN博客</a></p>
</blockquote>
<p>蚁群算法的创始人Dorigo在“Ant colony system: a cooperative learning approach to the traveling salesman problem”一文中提出了一种具有全新机制的ACO算法——蚁群系统（Ant Colony System，ACS），进一步提高了ACO算法的性能。</p>
<ol>
<li>使用一种<strong>伪随机比例规则</strong>（pseudorandom proportional）选择下城市节点，建立开发当前路径与探索新路径之间的平衡。地图上的蚂蚁r，u寻找下一个城市s，q是均匀分布。</li>
</ol>
<p>$$
s= {\begin{matrix}arg{max_{u \epsilon J_k(r)}} \begin{Bmatrix}[\tau(r,u)]^\alpha[\eta(r,u)]^\beta\end{Bmatrix} &amp;if q\le q_0 \S &amp; otherwise\end{matrix}.
$$</p>
<p>$$
p_k(r,s) = {\begin{matrix}\frac{[\tau(r,u)]^\alpha[\eta(r,u)]^\beta}{\sum_{u\epsilon J_k(r)}[\tau(r,u)]^\alpha[\eta(r,u)]^\beta}  &amp; if s \epsilon J_k(r)\0 &amp; otherwise\end{matrix}.
$$</p>
<ol>
<li><strong>使用信息素全局更新规则</strong>，每轮迭代中所有蚂蚁都已构建完路径后，在属于至今最优路径的边上蒸发和释放信息素。</li>
</ol>
<p>$$
\tau(r,s)=(1-\alpha)\tau(r,s)+\alpha\Delta\tau(r,s).
$$</p>
<p>$$
\Delta\tau(r,s)={\begin{matrix}(L_{gb})^-1  &amp; if s (r, s)\epsilon path_{global-best}\0 &amp; otherwise\end{matrix}.
$$</p>
<ol>
<li>引入信息素局部更新规则，在路径构建过程中，对每一只蚂蚁，每当其经过一条边(i, j)时，它将立刻对这条边进行信息素的更新。</li>
</ol>
<p>$$
\tau(r,s)=(1-\rho)\tau(r,s)+\rho\Delta\tau(r,s).
$$</p>
<h4 id="基于排列的蚂蚁系统asrank">基于排列的蚂蚁系统ASrank</h4>
<p>在AS的基础上给蚂蚁要释放的信息素大小加上一个权值，进一步加大各边信息素量的差异，以指导搜索。在每一轮所有蚂蚁构建完路径后，它们将按照所得路径的长短进行排名，只有生成了至今最优路径的蚂蚁和排名在前(ω-1)的蚂蚁才被允许释放信息素，蚂蚁在边(i, j)上释放的信息素 的权值由蚂蚁的排名决定。权值(ω−k)对不同路径的信息素浓度差异起到了一个放大的作用，AS_rank能更有力度地指导蚂蚁搜索。</p>
<h4 id="连续正交蚁群系统coac">连续正交蚁群系统COAC</h4>
<p>COAC通过在问题空间内自适应地选择和调整一定数量的区域，并利用蚂蚁在这些区域内进行正交搜索、在区域间进行状态转移、并更新各个区域的信息素来搜索问题空间中的最优解。</p>
<h2 id="应用">应用</h2>
<ol>
<li>车辆路径问题（vehicle routing problem，VRP）</li>
<li>生产调度问题（Product Scheduling Problem，PSP）</li>
<li>图像处理（图像特征提取、图像分割、图像恢复……）</li>
<li>机器人路径规划</li>
<li>聚类问题</li>
<li>网络路由</li>
<li>…</li>
</ol>
<h2 id="aco最新研究情况">ACO最新研究情况</h2>
<p><a href="https://www.notion.so/ACO-b97a3cbf3fc9456caaf2db9265d0feee" target="_blank">ACO最新研究情况</a></p>
<h2 id="参考文献">参考文献</h2>
<ol>
<li><a href="https://zhuanlan.zhihu.com/p/404181189" target="_blank">https://zhuanlan.zhihu.com/p/404181189</a></li>
<li><a href="https://zhuanlan.zhihu.com/p/137408401" target="_blank">https://zhuanlan.zhihu.com/p/137408401</a></li>
<li>肖艳秋,焦建强,乔东平,杜江恒,周坤.蚁群算法的基本原理及应用综述[J].轻工科技,2018,34(03):69-72.</li>
</ol>
    </div>
</article>




            </div>
            <aside class="col-12 col-md-3 float-left sidebar">
    
    <div class="sidebar-item sidebar-pages">
        <h3>页面</h3>
        <ul>
            
            <li>
                <a href="/">Home</a>
            </li>
            
            <li>
                <a href="/archives/">Archives</a>
            </li>
            
            <li>
                <a href="/about/">About</a>
            </li>
            
            <li>
                <a href="/search/">Search</a>
            </li>
            
            <li>
                <a href="/index.xml">RSS</a>
            </li>
            
        </ul>
    </div>
    
    <div class="sidebar-item sidebar-links">
        <h3>链接</h3>
        <ul>
            
            <li>
                <a href="https://github.com/ruaqy" target="_blank"><span>GitHub</span></a>
            </li>
            
            <li>
                <a href="https://gitee.com/ruqy" target="_blank"><span>Gitee</span></a>
            </li>
            
            <li>
                <a href="https://space.bilibili.com/13382902" target="_blank"><span>Bilibili</span></a>
            </li>
            
        </ul>
    </div>
    
    <div class="sidebar-item sidebar-tags">
        <h3>标签</h3>
        <div>
            
            <span>
                <a href="/tags/dl/">DL</a>
            </span>
            
            <span>
                <a href="/tags/make-up/">Make Up</a>
            </span>
            
            <span>
                <a href="/tags/matlab/">MATLAB</a>
            </span>
            
            <span>
                <a href="/tags/mindspore/">mindspore</a>
            </span>
            
            <span>
                <a href="/tags/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/">机器学习</a>
            </span>
            
        </div>
    </div>
    <div class="sidebar-item sidebar-toc">
        <h3>目录</h3><nav id="TableOfContents">
  <ul>
    <li><a href="#概述">概述</a></li>
    <li><a href="#基本模型">基本模型</a>
      <ul>
        <li><a href="#蚂蚁">蚂蚁</a></li>
        <li><a href="#信息素">信息素</a></li>
        <li><a href="#信息素更新法则">信息素更新法则</a></li>
      </ul>
    </li>
    <li><a href="#应用">应用</a></li>
    <li><a href="#aco最新研究情况">ACO最新研究情况</a></li>
    <li><a href="#参考文献">参考文献</a></li>
  </ul>
</nav></div>
</aside>

        </div>
        <div class="btn">
    <div class="btn-menu" id="btn-menu">
        <i class="iconfont icon-grid-sharp"></i>
    </div>
    <div class="btn-toggle-mode">
        <i class="iconfont icon-contrast-sharp"></i>
    </div>
    <div class="btn-scroll-top">
        <i class="iconfont icon-chevron-up-circle-sharp"></i>
    </div>
</div>
<aside class="sidebar-mobile" style="display: none;">
  <div class="sidebar-wrapper">
    
    <div class="sidebar-item sidebar-pages">
        <h3>页面</h3>
        <ul>
            
            <li>
                <a href="/">Home</a>
            </li>
            
            <li>
                <a href="/archives/">Archives</a>
            </li>
            
            <li>
                <a href="/about/">About</a>
            </li>
            
            <li>
                <a href="/search/">Search</a>
            </li>
            
            <li>
                <a href="/index.xml">RSS</a>
            </li>
            
        </ul>
    </div>
    
    <div class="sidebar-item sidebar-links">
        <h3>链接</h3>
        <ul>
            
            <li>
                <a href="https://github.com/ruaqy" target="_blank"><span>GitHub</span></a>
            </li>
            
            <li>
                <a href="https://gitee.com/ruqy" target="_blank"><span>Gitee</span></a>
            </li>
            
            <li>
                <a href="https://space.bilibili.com/13382902" target="_blank"><span>Bilibili</span></a>
            </li>
            
        </ul>
    </div>
    
    <div class="sidebar-item sidebar-tags">
        <h3>标签</h3>
        <div>
            
            <span>
                <a href="/tags/dl/">DL</a>
            </span>
            
            <span>
                <a href="/tags/make-up/">Make Up</a>
            </span>
            
            <span>
                <a href="/tags/matlab/">MATLAB</a>
            </span>
            
            <span>
                <a href="/tags/mindspore/">mindspore</a>
            </span>
            
            <span>
                <a href="/tags/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/">机器学习</a>
            </span>
            
        </div>
    </div>
    
    
    
    <div class="sidebar-item sidebar-toc">
        <h3>目录</h3>
        <nav id="TableOfContents">
  <ul>
    <li><a href="#概述">概述</a></li>
    <li><a href="#基本模型">基本模型</a>
      <ul>
        <li><a href="#蚂蚁">蚂蚁</a></li>
        <li><a href="#信息素">信息素</a></li>
        <li><a href="#信息素更新法则">信息素更新法则</a></li>
      </ul>
    </li>
    <li><a href="#应用">应用</a></li>
    <li><a href="#aco最新研究情况">ACO最新研究情况</a></li>
    <li><a href="#参考文献">参考文献</a></li>
  </ul>
</nav>
    </div>
    
    
  </div>
</aside>
    </main>

    <footer>
    <div class="container-lg clearfix">
        <div class="col-12 footer">
            
            <p>
                除特殊注明部分，本站内容采用 <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 进行许可。
            </p>
            
            <span>&copy; 2023-2023
                <a href="/">RQY</a>
                 | <a href="https://github.com/dsrkafuu/hugo-theme-fuji">Source code</a> 
                | 基于 <a href="https://github.com/dsrkafuu/hugo-theme-fuji/"
                   target="_blank">Fuji-v2</a> &amp; <a href="https://gohugo.io/"
                                                    target="_blank">Hugo</a> 构建
            </span>
        </div>
    </div>
</footer>

    
<script defer src="https://cdn.jsdelivr.net/npm/medium-zoom@1.0.6/dist/medium-zoom.min.js" integrity="sha512-N9IJRoc3LaP3NDoiGkcPa4gG94kapGpaA5Zq9/Dr04uf5TbLFU5q0o8AbRhLKUUlp8QFS2u7S+Yti0U7QtuZvQ==" crossorigin="anonymous"></script>
<script defer src="https://cdn.jsdelivr.net/npm/lazysizes@5.3.2/lazysizes.min.js" integrity="sha512-q583ppKrCRc7N5O0n2nzUiJ+suUv7Et1JGels4bXOaMFQcamPk9HjdUknZuuFjBNs7tsMuadge5k9RzdmO+1GQ==" crossorigin="anonymous"></script>
<script defer src="https://cdn.jsdelivr.net/npm/prismjs@1.27.0/components/prism-core.min.js" integrity="sha512-LCKPTo0gtJ74zCNMbWw04ltmujpzSR4oW+fgN+Y1YclhM5ZrHCZQAJE4quEodcI/G122sRhSGU2BsSRUZ2Gu3w==" crossorigin="anonymous"></script>
<script defer src="https://cdn.jsdelivr.net/npm/prismjs@1.27.0/plugins/autoloader/prism-autoloader.min.js" integrity="sha512-GP4x8UWxWyh4BMbyJGOGneiTbkrWEF5izsVJByzVLodP8CuJH/n936+yQDMJJrOPUHLgyPbLiGw2rXmdvGdXHA==" crossorigin="anonymous"></script>



<script defer src="/assets/js/fuji.min.645f1123be695831f419ab54c1bcba327325895c740014006e57070d4f3e5d6b553e929c4b46f40ea707249e9c7f7c2a446d32a39ce7319f80a34525586a8e0f.js" integrity="sha512-ZF8RI75pWDH0GatUwby6MnMliVx0ABQAblcHDU8&#43;XWtVPpKcS0b0DqcHJJ6cf3wqRG0yo5znMZ&#43;Ao0UlWGqODw=="></script>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.15.3/dist/katex.min.css" integrity="sha512-07YhC3P4/vS5HdgGuNAAeIxb5ee//efgRNo5AGdMtqFBUPYOdQG/sDK0Nl5qNq94kdEk/Pvu8pmN4GYUeucUkw==" crossorigin="anonymous">
<script src="https://cdn.jsdelivr.net/npm/katex@0.15.3/dist/katex.min.js" integrity="sha512-aMDiFsrEV3KzAn9EHwyBRS7y1APjZWt/Z/73ukLN2Ca2KcGGzlOQFQSnfOdnEcehpwMaQ8edlDB/0cMX2GsHbg==" crossorigin="anonymous"></script>
<script src="https://cdn.jsdelivr.net/npm/katex@0.15.3/dist/contrib/auto-render.min.js" integrity="sha512-ZA/RPrAo88DlwRnnoNVqKINnQNcWERzRK03PDaA4GIJiVZvGFIWQbdWCsUebMZfkWohnfngsDjXzU6PokO4jGw==" crossorigin="anonymous"></script>
<script>
  renderMathInElement(document.querySelector('div.content'), {
    delimiters: [
      { left: '$$', right: '$$', display: true },
      { left: '\\[', right: '\\]', display: true },
      { left: '$', right: '$', display: false },
      { left: '\\(', right: '\\)', display: false },
    ],
  });
</script>




</body>

</html>
